/**
*This program is an implementation of Kruskal's Algorithm for
determining a minimal spanning tree for a connected, non-directed,
weighted graph.    
*/

#include <stdio.h>
/*! Number of vertices
*/
#define N 6                      

/*! Number of Edges in graph
*/
#define M 15                     

int U[N];

/*! function prototypes 
*/
void makeset (int i);
int find (int i);
void merge (int p, int q);
int equal (int p, int q);
void initial (int n);
void test_univ (void);
/*! Used for test purposes
*/
void pause (void);                
/*! function definitions 
*/
int main()
{
/*! weighted graphs  
*/
int W[N][N] = {0,2,4,1,3,2,    
                  2,0,6,4,5,1,
                  4,6,0,4,2,1,
                  1,4,4,0,5,4,
                  3,5,2,5,0,6,
                  2,1,1,4,6,0};
   int E[M][3];                   /* complete set of edges */
   int F[N-1][3];                 /* set of edges in min. span. tree */
   int num_edges = 0;             /* num of edges in min. span. tree */
   int next_edge = 0;             /* initially next edge not  considered */
   int weight = 0;                /* minimal spanning tree weight */
   int a, b, c, i, j, k;         
/*!initialize set of edges 
*/
   k = 0;
   for (i = 0; i < N; i++)
      for (j = 0; j < N; j++)
         if (j > i)
         {  E[k][0] = i;          /* first vertex of edge */
            E[k][1] = j;          /* second vertex of edge */
            E[k][2] = W[i][j];    /* weight of edge */
            k++;
         }

/*! display set of edges - before sort 
*/
   printf("edges before sort\n");
   for (i = 0; i < M; i++)
   {  for (j = 0; j < 3; j++)
         printf(" %3d", E[i][j]);
      printf("\n");
   }
   
   pause();
   
/*! sort set of edges in non-decreasing order by weight - bubblesort 
*/

   for (i = M - 1; i > 0; i--)
      for (j = 0; j < i; j++)
         if (E[j][2] > E[j+1][2])
         {  a = E[j][0];
            b = E[j][1];
            c = E[j][2];
            E[j][0] = E[j+1][0];
            E[j][1] = E[j+1][1];
            E[j][2] = E[j+1][2];
            E[j+1][0] = a;
            E[j+1][1] = b;
            E[j+1][2] = c;   
         }

/*! display set of edges - after sort 
  */
   printf("After Sort:\n");
   for (i = 0; i < M; i++)
   {  for (j = 0; j < 3; j++)
         printf(" %3d", E[i][j]);
      printf("\n");
   }
   
/*! create n disjoint subsets 
*/
  initial (N);
   
/*! initialize set of edges in min. span. tree to empty 
*/
   for (i = 0; i < N - 1; i++)
      for (j = 0; j < 3; j++)
         F[i][j] = -1;            /* '-1' denotes 'empty' */
   
 test_univ();         
         
/*! find minimal spanning tree 
*/
   while (num_edges < N - 1)
   {  a = E[next_edge][0];
      b = E[next_edge][1];
      
      i = find(a);
      j = find(b);
      
      if (!equal(i, j))
      {  merge (i, j);
         F[num_edges][0] = E[next_edge][0];
         F[num_edges][1] = E[next_edge][1];
         F[num_edges][2] = E[next_edge][2];
         num_edges++;
         
         test_univ();
      }
      
      next_edge++;
   }
   
/*! display edges comprising minimal spanning tree 
*/
   printf("\nMinimal Spanning Tree Edges:\n");
   printf("F = (");
   for (i = 0; i < N - 1; i++)
   {  printf("(V%d,V%d)", F[i][0], F[i][1]);
      if (i < N - 2)
         printf(", ");
      weight = weight + F[i][2];
   }
   printf(")\n");
   printf("Minimal Spanning Tree Weight = %d\n", weight);
   
   return (0);
}
/*! makeset() 
*/
void makeset (int i)
{  U[i] = i;
}

/*! find() 
*/
int find (int i)
{  int j;

   j = i;
   while (U[j] != j)
      j = U[j];
   return (j);
}

/*! merge() 
*/
void merge (int p, int q)
{  if (p < q)
      U[q] = p;
   else
      U[p] = q;
}

/*! equal() 
*/
int equal (int p, int q)
{  if (p == q)
      return (1);
   else
      return (0);
}

/*! initial() 
*/
void initial (int n)
{  int i;

   for (i = 0; i < n; i++)
      makeset(i);
}

/*! test() 
*/

void test_univ (void)

                         /*! test universe values */

{  int i;

  // printf("\nThe disjoint subsets are:\n");
   //for (i = 0; i < N; i++)
   //      printf(" %3d", U[i]);
   //   printf("\n");
}

/*! pause() 
*/
void pause (void)
{  int i;
    printf("Press ENTER to continue...\n");
   i = getchar();   
}


